package 代码随想录.数组;

import java.util.ArrayList;
import java.util.List;

public class _6螺旋矩阵II {
    /**
     * 59. 螺旋矩阵 II
     * https://leetcode.cn/problems/spiral-matrix-ii/
     * 给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     */
    public int[][] generateMatrix(int n) {
        if(n==1)
            return new int[][]{{1}};
        int[][] res = new int[n][n];
        int left = 0 , right = n-1;
        int top = 0 , bottom = n-1;
        int k = 1;
        while(left<=right || top <= bottom){
            for(int i=left;i<=right;i++)
                res[top][i] = k++;
            top++;
            if(top>bottom)
                break;
            for(int i=top;i<=bottom;i++)
                res[i][right] = k++;
            right--;
            if(right<left)
                break;
            for(int i=right;i>=left;i--)
                res[bottom][i] = k++;
            bottom--;
            if(bottom<top)
                break;
            for(int i=bottom;i>=top;i--)
                res[i][left] = k++;
            left++;
            if(left>right)
                break;
        }
        return res;
    }

    /**
     * 54. 螺旋矩阵
     * https://leetcode.cn/problems/spiral-matrix/
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if(matrix.length==0)
            return res;
        int left = 0 , right = matrix[0].length-1;
        int top = 0 , bottom = matrix.length - 1;
        while(left<=right && top<=bottom){
            for(int i=left;i<=right;i++)
                res.add(matrix[top][i]);
            top++;
            if(top>bottom)
                break;
            for(int i=top;i<=bottom;i++)
                res.add(matrix[i][right]);
            right--;
            if(right<left)
                break;
            for(int i=right;i>=left;i--)
                res.add(matrix[bottom][i]);
            bottom--;
            if(bottom<top)
                break;
            for(int i=bottom;i>=top;i--)
                res.add(matrix[i][left]);
            left++;
            if(left>right)
                break;
        }
        return res;
    }

    /**
     * 剑指 Offer 29. 顺时针打印矩阵
     * https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
     */
    public int[] spiralOrder2(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if(matrix.length==0)
            return new int[0];
        int left = 0 , right = matrix[0].length-1;
        int top = 0 , bottom = matrix.length - 1;
        while(left<=right && top<=bottom){
            for(int i=left;i<=right;i++)
                res.add(matrix[top][i]);
            top++;
            if(top>bottom)
                break;
            for(int i=top;i<=bottom;i++)
                res.add(matrix[i][right]);
            right--;
            if(right<left)
                break;
            for(int i=right;i>=left;i--)
                res.add(matrix[bottom][i]);
            bottom--;
            if(bottom<top)
                break;
            for(int i=bottom;i>=top;i--)
                res.add(matrix[i][left]);
            left++;
            if(left>right)
                break;
        }
        int[] arr = new int[res.size()];
        for(int i=0;i<res.size();i++)
            arr[i] = res.get(i);
        return arr;
//        return res.toArray(new Integer[res.size()]);
    }
}
